package lru

/**
lru算法
https://leetcode.cn/problems/lru-cache/

lru淘汰算法的原理是，当数据满的时候，进来新数据，淘汰最早且访问最少的数据。

算法原理：
-

*/

type DBListNode struct {
	Key    int
	Val    int
	Front  *DBListNode
	Behind *DBListNode
}

type LRUCache struct {
	Capacity int
	Length   int
	Search   map[int]*DBListNode
	Head     *DBListNode
	Tail     *DBListNode
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		Capacity: capacity,
		Search:   make(map[int]*DBListNode),
	}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.Search[key]; ok {
		this.Refresh(node)
		return node.Val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {

	if this.Get(key) == -1 {
		node := &DBListNode{
			Key: key,
			Val: value,
		}
		if this.Capacity == this.Length {
			this.Head.Front = node
			node.Behind = this.Head
			this.Head = node

			delete(this.Search, this.Tail.Key)
			this.Search[key] = node

			this.Tail = this.Tail.Front
			this.Tail.Behind.Front = nil
			this.Tail.Behind = nil
		} else {
			this.Length++
			this.Search[key] = node
			if this.Head == nil {
				this.Head = node
			} else {
				node.Behind = this.Head
				this.Head.Front = node
				this.Head = node
			}

			if this.Tail == nil {
				this.Tail = node
			}
		}
	} else {
		if this.Search[key].Val != value {
			this.Search[key].Val = value
		}
	}
}

func (this *LRUCache) Refresh(node *DBListNode) {
	if node.Front != nil {
		if node == this.Tail {
			// 如果node是尾部,直接把尾部替换
			this.Tail = node.Front
		} else {
			node.Behind.Front = node.Front
		}

		node.Front.Behind = node.Behind

		node.Behind = this.Head
		node.Front = nil
		this.Head.Front = node
		this.Head = node
	}
}
